package com.javaDemo.ti;

import com.javaDemo.node.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

/**
 * @ClassName: Chongjianshu
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * @Auther: csy
 * @Date: 2020/7/1 13:41
 * @Description:
 */
public class Chongjianshu {
    public static void main(String[] args) {
        int[] preorder={3,9,4,5,2,6};
        int[] inorder={5,4,9,2,3,6};
        System.out.println(buildTree(preorder,inorder));
    }
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int length = preorder.length;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }

    class Solution {
        int[] preorder;
        HashMap<Integer, Integer> dic = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for(int i = 0; i < inorder.length; i++)
                dic.put(inorder[i], i);
            return recur(0, 0, inorder.length - 1);
        }
        TreeNode recur(int root, int left, int right) {
            if(left > right) return null;                          // 递归终止
            TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
            int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
            node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
            node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
            return node;                                           // 回溯返回根节点
        }
    }

    //https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/chao-ji-rong-yi-dong-de-di-gui-by-yusael-ahnb/
    public TreeNode buildTrees(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        // [先序遍历]可以直接知道：根节点的值 rootVal
        int rootVal = preorder[0]; // 3
        // 在[中序遍历]中寻找 rootVal 的索引
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i; // 3
                break;
            }
        }
        // 构造根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归
        // [9, 6, 10]
        // [6, 9, 10]
        root.left = buildTrees(Arrays.copyOfRange(preorder, 1, rootIndex + 1), Arrays.copyOfRange(inorder, 0, rootIndex));
        // [20, 15, 7]
        // [15, 20, 7]
        root.right = buildTrees(Arrays.copyOfRange(preorder, rootIndex + 1, preorder.length), Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length));
        return root;
    }
}
